package org.algorithm.dac;

public class HanioTower {
    public static void main(String[] args) {
        hanioTower(50, 'A', 'B', 'C');
    }


    /**
     * 1.利用分治算法，将所有盘子分成上部分和下部分
     * 2.将上部分从A放到B，A->B
     * 3.将下部分从A放到C. A->C
     * 4.最后将B放到C。   B->C
     */
    public static void hanioTower(int num, char a, char b, char c) {
        if (num == 1) {
            System.err.println("第1个盘从 " + a + "->" + c);
        } else {


            // TODO: 2022/3/3 通过num%2的思想，算出第一步是放到b或c
            hanioTower(num - 1, a, c, b);
            // TODO: 2022/3/3 直接从a->c
            System.err.println("第" + num + "个盘从 " + a + "->" + c);
            // TODO: 2022/3/3 计算出从哪个位置开始回溯：就是将目标放到c后，所有盘要从B移动到它本身所在的位置，
            //  那么就是将b当作a，然后c还是c，然后计算将b-1上部分盘子放到b的位置(A),递归进行
            hanioTower(num - 1, b, a, c);
        }
    }
}
